/* UVA10677 POJ3027 Base Equality */

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

bool judge(int r, int b1, int b2)
{
    LL ret = 0, t = 1;
    int x = r;
    while (x)
    {
        ret += x % b1 * t;
        x /= b1;
        t *= b2;
    }

    return ret % r == 0;
}

int main()
{
    int n, b1, b2, r1, r2;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d%d%d", &b1, &b2, &r1, &r2);

        int ans = r1;
        for (int i = r1 + 1; i < r2; i++)
            if (judge(i, b1, b2))
                ans = i;

        if (ans == r1)
            printf("Non-existent.\n");
        else
            printf("%d\n", ans);
    }

    return 0;
}
